package leetcode.editor.week.week310;

import java.util.Arrays;
import java.util.PriorityQueue;

// 6178. 将区间分为最少组数
// https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/
class Solution6178 {
    // 贪心（TLE...）
    /*public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[] arr = new int[intervals.length];
        int idx = 0;
        for(int[] interval : intervals) {
            if(idx == 0) arr[idx++] = interval[1];
            else {
                boolean flag = false;

                for(int i = 0; i < idx; i++) {
                    if(arr[i] < interval[0]) {
                        arr[i] = interval[1];
                        flag = true;
                        break;
                    }
                }

                if(!flag) {
                    arr[idx++] = interval[1];
                }
            }
        }

        return idx;
    }*/

    // 贪心 + 堆
    // 对左边区间啊进行排序，充分利用空间，使用小顶堆来维护右边界
    // 能分到一组，开始时间小于等于上一个结束时间
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int[] interval : intervals) {
            // 不可以合并，那就先出队列
            if (!queue.isEmpty() && queue.peek() < interval[0]) queue.poll();
            // 更新或者增加分组
            queue.offer(interval[1]);
        }

        return queue.size();
    }

}